﻿//给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
//由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
//
//注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x** 0.5 。
//
//输入：x = 4
//输出：2
//
//输入：x = 8
//输出：2
//解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
//
//提示：
//	0 <= x <= 2^31 - 1

class Solution {
public:
    int mySqrt(int x) {
        // 由于两个较⼤的数相乘可能会超过int最⼤范围

        // 因此⽤long long
        long long i = 0;
        for (i = 0; i <= x; i++) {
            // 如果两个数相乘正好等于x，直接返回i
            if (i * i == x)
                return i;
            // 如果第⼀次出现两个数相乘⼤于x，说明结果是前⼀个数
            if (i * i > x)
                return i - 1;
            // 为了处理oj题需要控制所有路径都有返回值
        }
        return -1;
    }
};